{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Clone Binary Tree With Random Pointer"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #breadth-first-search #hash-table #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #广度优先搜索 #哈希表 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: copyRandomBinaryTree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #克隆含随机指针的二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个二叉树，树中每个节点都含有一个附加的随机指针，该指针可以指向树中的任何节点或者指向空（<code>null</code>）。</p>\n",
    "\n",
    "<p>请返回该树的 <strong><a href=\"https://baike.baidu.com/item/%E6%B7%B1%E6%8B%B7%E8%B4%9D/22785317?fr=aladdin\" target=\"_blank\">深拷贝</a></strong> 。</p>\n",
    "\n",
    "<p>该树的输入/输出形式与普通二叉树相同，每个节点都用 <code>[val, random_index]</code> 表示：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>val</code>：表示 <code>Node.val</code> 的整数</li>\n",
    "\t<li><code>random_index</code>：随机指针指向的节点（在输入的树数组中）的下标；如果未指向任何节点，则为 <code>null</code> 。</li>\n",
    "</ul>\n",
    "\n",
    "<p>该树以 <code>Node</code> 类的形式给出，而你需要以 <code>NodeCopy</code> 类的形式返回克隆得到的树。<code>NodeCopy</code> 类和<code>Node</code> 类定义一致。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode.com/uploads/2020/06/17/clone_1.png\" style=\"height: 473px; width: 500px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [[1,null],null,[4,3],[7,0]]\n",
    "<strong>输出：</strong>[[1,null],null,[4,3],[7,0]]\n",
    "<strong>解释：</strong>初始二叉树为 [1,null,4,7] 。\n",
    "节点 1 的随机指针指向 null，所以表示为 [1, null] 。\n",
    "节点 4 的随机指针指向 7，所以表示为 [4, 3] 其中 3 是树数组中节点 7 对应的下标。\n",
    "节点 7 的随机指针指向 1，所以表示为 [7, 0] 其中 0 是树数组中节点 1 对应的下标。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode.com/uploads/2020/06/17/clone_2.png\" style=\"height: 540px; width: 500px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [[1,4],null,[1,0],null,[1,5],[1,5]]\n",
    "<strong>输出：</strong>[[1,4],null,[1,0],null,[1,5],[1,5]]\n",
    "<strong>解释：</strong>节点的随机指针可以指向它自身。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/06/13/e2.png\" style=\"height: 426px; width: 500px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [[1,6],[2,5],[3,4],[4,3],[5,2],[6,1],[7,0]]\n",
    "<strong>输出：</strong>[[1,6],[2,5],[3,4],[4,3],[5,2],[6,1],[7,0]]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>tree</code> 中节点数目范围是 <code>[0, 1000]</code></li>\n",
    "\t<li>每个节点的值的范围是 <code>[1, 10^6]</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [clone-binary-tree-with-random-pointer](https://leetcode.cn/problems/clone-binary-tree-with-random-pointer/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [clone-binary-tree-with-random-pointer](https://leetcode.cn/problems/clone-binary-tree-with-random-pointer/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,null],null,[4,3],[7,0]]', '[[1,4],null,[1,0],null,[1,5],[1,5]]', '[[1,6],[2,5],[3,4],[4,3],[5,2],[6,1],[7,0]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for Node.\n",
    "# class Node:\n",
    "#     def __init__(self, val=0, left=None, right=None, random=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "#         self.random = random\n",
    "\n",
    "class Solution:\n",
    "    def copyRandomBinaryTree(self, root):\n",
    "        \"\"\"\n",
    "        深拷贝带有random指针的二叉树\n",
    "        Args:   \n",
    "            root (Node): 待拷贝的二叉树根节点\n",
    "        \n",
    "        returns (Node): 新创建的二叉树根节点\n",
    "        \"\"\"\n",
    "        #处理特殊情况\n",
    "        if root == None: return None \n",
    "        \n",
    "        node_dict = {}  #key: 原始二叉树的节点, value: 新建二叉树的所对应的复制的节点\n",
    "        queue = collections.deque()\n",
    "        new_root = NodeCopy(root.val)\n",
    "        node_dict[root] = new_root\n",
    "\n",
    "        queue.append(root)\n",
    "\n",
    "        #使用层序遍历, 复制二叉树\n",
    "        while len(queue):\n",
    "            cur_node = queue.popleft()\n",
    "            copy_cur_node = node_dict[cur_node]\n",
    "\n",
    "            if cur_node.left != None:\n",
    "                new_node = NodeCopy(cur_node.left.val)\n",
    "                node_dict[cur_node.left] = new_node\n",
    "                copy_cur_node.left = new_node    \n",
    "                queue.append(cur_node.left)\n",
    "\n",
    "            if cur_node.right != None:\n",
    "                new_node = NodeCopy(cur_node.right.val)\n",
    "                node_dict[cur_node.right] = new_node\n",
    "                copy_cur_node.right = new_node \n",
    "                queue.append(cur_node.right)\n",
    "\n",
    "        # print(node_dict)\n",
    "        #利用字典, 重新连接random指针\n",
    "        for orign_node, copy_node in node_dict.items():\n",
    "            if orign_node.random in node_dict.keys():\n",
    "                copy_node.random = node_dict[orign_node.random] \n",
    "        \n",
    "        #return\n",
    "        return new_root\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for Node.\n",
    "# class Node:\n",
    "#     def __init__(self, val=0, left=None, right=None, random=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "#         self.random = random\n",
    "\n",
    "class Solution:\n",
    "    def copyRandomBinaryTree(self, root: 'Optional[Node]') -> 'Optional[NodeCopy]':\n",
    "        dct = {None:None}\n",
    "        def f(o):\n",
    "            if not o: return None\n",
    "            dct[o] = NodeCopy(o.val, f(o.left), f(o.right))\n",
    "            return dct[o]\n",
    "        ans = f(root)\n",
    "        for k, v in dct.items():\n",
    "            if k: v.random = dct[k.random]\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def copyRandomBinaryTree(self, root: 'Optional[Node]') -> 'Optional[NodeCopy]':\n",
    "        def build(root):\n",
    "            if not root:\n",
    "                return None\n",
    "            cur = NodeCopy(root.val, build(root.left), build(root.right))\n",
    "            log[root] = cur\n",
    "            return cur\n",
    "        \n",
    "        log = {}\n",
    "        build(root)\n",
    "        for k, v in log.items():\n",
    "            v.random = log.get(k.random, None)\n",
    "\n",
    "        return log.get(root, None)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for Node.\n",
    "# class Node:\n",
    "#     def __init__(self, val=0, left=None, right=None, random=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "#         self.random = random\n",
    "\n",
    "class Solution:\n",
    "    def copyRandomBinaryTree(self, root: 'Optional[Node]') -> 'Optional[NodeCopy]':\n",
    "        visited=dict()\n",
    "        def dfs(T):\n",
    "            if not T:\n",
    "                return\n",
    "            if T in visited:\n",
    "                return visited[T]\n",
    "            a=NodeCopy(T.val)\n",
    "            visited[T]=a\n",
    "            a.left=dfs(T.left)\n",
    "            a.right=dfs(T.right)\n",
    "            a.random=dfs(T.random)\n",
    "            return a\n",
    "        return dfs(root)\n",
    "            \n",
    "            \n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for Node.\n",
    "# class Node:\n",
    "#     def __init__(self, val=0, left=None, right=None, random=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "#         self.random = random\n",
    "\n",
    "class Solution:\n",
    "    def copyRandomBinaryTree(self, root: 'Optional[Node]') -> 'Optional[NodeCopy]':\n",
    "        seen = dict()\n",
    "        def dfs(root: 'Node') -> 'NodeCopy':\n",
    "            if root == None:\n",
    "                return None\n",
    "            if root in seen:\n",
    "                return seen[root]\n",
    "            cur = NodeCopy(root.val)\n",
    "            seen[root] = cur \n",
    "            cur.left = dfs(root.left)\n",
    "            cur.right = dfs(root.right)\n",
    "            cur.random = dfs(root.random)\n",
    "            return cur \n",
    "        return dfs(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class Node:\n",
    "#     def __init__(self, val=0, left=None, right=None, random=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "#         self.random = random\n",
    "class Solution:\n",
    "    def copyRandomBinaryTree(self, root: 'Node') -> 'NodeCopy':\n",
    "        seen = dict()\n",
    "\n",
    "        def dfs(root: 'Node') -> 'NodeCopy':\n",
    "            if root == None:\n",
    "                return None\n",
    "            if root in seen:\n",
    "                return seen[root]\n",
    "            cur = NodeCopy(root.val)\n",
    "            seen[root] = cur            #早入seen。最后再入就溢出了\n",
    "            cur.left = dfs(root.left)\n",
    "            cur.right = dfs(root.right)\n",
    "            cur.random = dfs(root.random)\n",
    "            return cur\n",
    "        return dfs(root)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for Node.\n",
    "# class Node:\n",
    "#     def __init__(self, val=0, left=None, right=None, random=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "#         self.random = random\n",
    "\n",
    "class Solution:\n",
    "    def copyRandomBinaryTree(self, root: 'Optional[Node]') -> 'Optional[NodeCopy]':\n",
    "        def dfs(root):\n",
    "            if not root: return None\n",
    "            if root in node_map: return node_map[root]\n",
    "            # result = NodeCopy(root.val, dfs(root.left), dfs(root.right), dfs(root.random)) # 1WA: this will result in infinite recursion\n",
    "            result = NodeCopy(root.val)\n",
    "            node_map[root] = result\n",
    "            result.left = dfs(root.left)\n",
    "            result.right = dfs(root.right)\n",
    "            result.random = dfs(root.random)\n",
    "            return result\n",
    "        \n",
    "        node_map = {}\n",
    "        return dfs(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for Node.\n",
    "# class Node:\n",
    "#     def __init__(self, val=0, left=None, right=None, random=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "#         self.random = random\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def copyRandomBinaryTree(self, root: 'Optional[Node]') -> 'Optional[NodeCopy]':\n",
    "        dict_ = dict()\n",
    "        if not root:\n",
    "            return None\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return\n",
    "            if root in dict_:\n",
    "                return dict_[root]\n",
    "            tmp = NodeCopy(root.val)\n",
    "            dict_[root] = tmp\n",
    "            dict_[root].left = dfs(root.left)\n",
    "            dict_[root].right = dfs(root.right)\n",
    "            dict_[root].random = dfs(root.random)\n",
    "            return tmp\n",
    "        \n",
    "        def dfs_2(root):\n",
    "            if not root:\n",
    "                return\n",
    "            if root.random:\n",
    "                dict_[root].random = dict_[root.random]\n",
    "            dfs_2(root.left)\n",
    "            dfs_2(root.right)\n",
    "        \n",
    "        head = dfs(root)\n",
    "        return head\n",
    "\n",
    "            \n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\r\n",
    "# class Node:\r\n",
    "#     def __init__(self, val=0, left=None, right=None, random=None):\r\n",
    "#         self.val = val\r\n",
    "#         self.left = left\r\n",
    "#         self.right = right\r\n",
    "#         self.random = random\r\n",
    "class Solution:\r\n",
    "    def copyRandomBinaryTree(self, root: 'Node') -> 'NodeCopy':\r\n",
    "        seen = dict()\r\n",
    "\r\n",
    "        def dfs(root: 'Node') -> 'NodeCopy':\r\n",
    "            if root == None:\r\n",
    "                return None\r\n",
    "            if root in seen:\r\n",
    "                return seen[root]\r\n",
    "            cur = NodeCopy(root.val)\r\n",
    "            seen[root] = cur            #早入seen。最后再入就溢出了\r\n",
    "            cur.left = dfs(root.left)\r\n",
    "            cur.right = dfs(root.right)\r\n",
    "            cur.random = dfs(root.random)\r\n",
    "            return cur\r\n",
    "\r\n",
    "        return dfs(root)\r\n",
    "\r\n",
    "    def copyRandomBinaryTree2(self, root: 'Node') -> 'NodeCopy':\r\n",
    "        if root == None:\r\n",
    "            return None\r\n",
    "        new_root = NodeCopy(root.val)\r\n",
    "        seen = dict()\r\n",
    "        seen[root] = new_root\r\n",
    "\r\n",
    "        Q = [root]\r\n",
    "        while Q:\r\n",
    "            x = Q.pop(0)\r\n",
    "\r\n",
    "            if x.left:\r\n",
    "                Q.append(x.left)\r\n",
    "                seen[x].left = seen[x.left] = NodeCopy(x.left.val)  #指针的关系，不断链\r\n",
    "            if x.right:\r\n",
    "                Q.append(x.right)\r\n",
    "                seen[x].right = seen[x.right] = NodeCopy(x.right.val)\r\n",
    "        \r\n",
    "        for n, ncopy in seen.items():\r\n",
    "            if n.random in seen.keys():\r\n",
    "                ncopy.random = seen[n.random]\r\n",
    "\r\n",
    "        return new_root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for Node.\n",
    "# class Node:\n",
    "#     def __init__(self, val=0, left=None, right=None, random=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "#         self.random = random\n",
    "\n",
    "class Solution:\n",
    "    def copyRandomBinaryTree(self, root: 'Optional[Node]') -> 'Optional[NodeCopy]':\n",
    "        if root == None:\n",
    "            return None\n",
    "        prevlist = []\n",
    "        copylist = []\n",
    "        def dfs(node, lst):\n",
    "            if node == None:\n",
    "                return\n",
    "            lst.append(node)\n",
    "            dfs(node.left, lst)\n",
    "            dfs(node.right, lst)\n",
    "        res = NodeCopy(val = root.val)\n",
    "        def foo(r, node):\n",
    "            if node.left == None:\n",
    "                r.left = None\n",
    "            else:\n",
    "                r.left = NodeCopy(val = node.left.val)\n",
    "                foo(r.left, node.left)\n",
    "            if node.right == None:\n",
    "                r.right = None\n",
    "            else:\n",
    "                r.right = NodeCopy(val = node.right.val)\n",
    "                foo(r.right, node.right)\n",
    "        foo(res, root)\n",
    "        dfs(root, prevlist)\n",
    "        dfs(res, copylist)\n",
    "        for i in range(len(prevlist)):\n",
    "            if prevlist[i].random == None:\n",
    "                copylist[i].random = None\n",
    "            else:\n",
    "                for j in range(len(prevlist)):\n",
    "                    if prevlist[i].random == prevlist[j]:\n",
    "                        copylist[i].random = copylist[j]\n",
    "                        break\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for Node.\n",
    "# class Node:\n",
    "#     def __init__(self, val=0, left=None, right=None, random=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "#         self.random = random\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def helper(self, root: 'Optional[Node]', visited: list):\n",
    "        if not root:\n",
    "            return None \n",
    "\n",
    "        if root in visited:\n",
    "            return visited[root]\n",
    "\n",
    "        copied = NodeCopy(val = root.val, left = None, right = None, random = None) # clone node with value\n",
    "        visited[root] = copied\n",
    "\n",
    "\n",
    "        copied.left = self.helper(root.left, visited)\n",
    "\n",
    "        copied.right = self.helper(root.right, visited)\n",
    "\n",
    "        copied.random = self.helper(root.random, visited)\n",
    "\n",
    "        return copied\n",
    "        \n",
    "    def copyRandomBinaryTree(self, root: 'Optional[Node]') -> 'Optional[NodeCopy]':\n",
    "        visited = dict() \n",
    "        return self.helper(root, visited)\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for Node.\n",
    "# class Node:\n",
    "#     def __init__(self, val=0, left=None, right=None, random=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "#         self.random = random\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.hashmap = {}\n",
    "\n",
    "    def copyRandomBinaryTree(self, root: 'Optional[Node]') -> 'Optional[NodeCopy]':\n",
    "        if root is None:\n",
    "            return None \n",
    "\n",
    "        if root in self.hashmap:\n",
    "            return self.hashmap[root]\n",
    "\n",
    "        rootCopy = NodeCopy(root.val)\n",
    "        self.hashmap[root] = rootCopy\n",
    "\n",
    "        rootCopy.left = self.copyRandomBinaryTree(root.left)\n",
    "        rootCopy.right = self.copyRandomBinaryTree(root.right)\n",
    "        rootCopy.random = self.copyRandomBinaryTree(root.random)\n",
    "\n",
    "        return rootCopy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for Node.\n",
    "# class Node:\n",
    "#     def __init__(self, val=0, left=None, right=None, random=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "#         self.random = random\n",
    "\n",
    "class Solution:\n",
    "    def copyRandomBinaryTree(self, root: 'Optional[Node]') -> 'Optional[NodeCopy]':\n",
    "        new_nodes = dict()\n",
    "\n",
    "        def dfs1(root):\n",
    "            if root is None:\n",
    "                new_nodes[None] = None\n",
    "                return\n",
    "            new_nodes[root] = NodeCopy(root.val)\n",
    "            dfs1(root.left)\n",
    "            dfs1(root.right)\n",
    "        \n",
    "        def dfs2(root):\n",
    "            if root is None:\n",
    "                return\n",
    "            new_root = new_nodes[root]\n",
    "            # print(new_root)\n",
    "            new_root.left = new_nodes[root.left]\n",
    "            new_root.right = new_nodes[root.right]\n",
    "            new_root.random = new_nodes[root.random]\n",
    "            dfs2(root.left)\n",
    "            dfs2(root.right)\n",
    "        \n",
    "        dfs1(root)\n",
    "        # print(new_nodes)\n",
    "        dfs2(root)\n",
    "        return new_nodes[root]\n",
    "        "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
